EVENTO
Algoritmos Quânticos para o Problema do Subgrupo Oculto Não Abeliano
Tipo de evento:
Defesa de Tese de Doutorado
Desde o surgimento do consagrado Algoritmo de Shor para a fatoração de números primos, a pesquisa de algoritmos quânticos tem recebido bastante atenção da comunidade científica. Uma das linhas de interesse desta área é a que trata do Problema do Subgrupo Oculto, PSO. Inicialmente se abordou este problema em grupos abelianos, resolvendo-o eficientemente através de um algoritmo quântico. Depois disso, a pesquisa avançou para o PSO em grupos não abelianos, onde desperta grande interesse, pois uma solução eficiente do PSO em certos grupos não abelianos implica em soluções eficientes de problemas como o Problema do Isomorfismo de Grafos e o Problema do Menor Vetor de um Reticulado. É no contexto do PSO não abeliano que desenvolvemos nossa pesquisa para a tese de doutorado. Em nosso trabalho, resolvemos eficientemente certas instancias do PSO não abeliano, atacando o problema no produto semidireto dos grupos cíclicos e , e também no produto semidireto de por , onde p é um número primo ímpar e N, r e s são inteiros positivos que satisfazem a certas propriedades. A estratégia que empregamos para a solução se utiliza de elementos já consolidados na literatura da área, como a Transformada de Fourier abeliana e o PSO abeliano, com um argumento que explora a estrutura algébrica do grupo onde atacamos o problema. O resultado dessa combinação é um algoritmo quântico eficiente para a solução do PSO nos grupos acima citados.
Data Início: 13/03/2008
Hora: 14:00
Data Fim: 13/03/2008
Hora: 17:30
Local: LNCC - Laboratório Nacional de Computação Ciêntifica - Auditorio A
Aluno:
Carlos Magno Martins Cosme - Universidade Federal dos Vales Gequitinhonha - UFVJM
Orientador:
Renato Portugal - Laboratório Nacional de Computação Científica - LNCC
Participante Banca Examinadora:
Carlile Campos Lavor - Universidade Estadual de Campinas - IMECC/UNICAMP
Gilson Antônio Giraldi - Laboratório Nacional de Computação Científica - LNCC
Guilherme Augusto de La Rocque Leal - IM-UFRJ - UFRJ
Renato Portugal - Laboratório Nacional de Computação Científica - LNCC
Suplente Banca Examinadora:
Marcelo Dutra Fragoso - Laboratório Nacional de Computação Científica - LNCC
Rubens Viana Ramos - DETIF-UFC - DETIF-UFC
